Codeforces Round #811 (Div. 3)

A

枚举 $i$ ，求出 $H:M$ 到 $h_i:m_i$ 时间长度的最小值即可。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 15;

int h[N], m[N], n, H, M, T;

int main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        cin >> n >> H >> M;
        for (int i = 1; i <= n; i++) cin >> h[i] >> m[i];
        int ansH = 24, ansM = 60;
        for (int i = 1; i <= n; i++) {
            int dtH = (h[i] + 24 - H) % 24;
            if (m[i] < M) dtH = (dtH ? dtH - 1 : 23 - dtH);
            int dtM = (m[i] + 60 - M) % 60;
            if (dtH * 60 + dtM < ansH * 60 + ansM) ansH = dtH, ansM = dtM;
        }
        cout << ansH << " " << ansM << endl;
    }
}

B

从后往前找第一个重复元素下标 $i$ ，删除 $[1,i]$ 即可。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

int T, n, a[N], vis[N];

int main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        memset(vis, 0, sizeof(vis));
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        int flag = 0;
        for (int i = n; i >= 1; i--) {
            if (vis[a[i]] == 0) vis[a[i]] = 1;
            else {
                flag = 1;
                cout << i << endl;
                break;
            }
        }
        if (flag == 0) cout << 0 << endl;
    }
}

C

注意到 $s\le 45$ ，直接打表即可。

Code

#include <bits/stdc++.h>
using namespace std;

int ans[50] = {
        0,
        1,
        2,
        3,
        4,
        5,
        6,
        7,
        8,
        9,
        19,
        29,
        39,
        49,
        59,
        69,
        79,
        89,
        189,
        289,
        389,
        489,
        589,
        689,
        789,
        1789,
        2789,
        3789,
        4789,
        5789,
        6789,
        16789,
        26789,
        36789,
        46789,
        56789,
        156789,
        256789,
        356789,
        456789,
        1456789,
        2456789,
        3456789,
        13456789,
        23456789,
        123456789
}, T, s;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &s);
        printf("%d\n", ans[s]);
    }
}

D

考虑dp。设 $f_i$ 为把前 $i$ 个字符染红的最小代价，转移方程显然

$f_i=\min\limits_{l=i-|s_j|}^{i-1}\{f_i,f_l+1\}$

记录转移点和染的颜色即可。

Code

#include<bits/stdc++.h>
using namespace std;

const int N = 105;
const int INF = 0x3f3f3f3f;

string t, s[N];
int T, f[N], len[N], pre[N], n, k;
pair<int, int> a[N];

void init() {
    for (int i = 0; i < N; i++) {
        f[i] = INF;
        pre[i] = len[i] = 0;
        a[i] = {0, 0};
    }
}

bool check(int i, int j) {
    return i >= len[j] && t.substr(i - len[j] + 1, len[j]) == s[j];
}

void solve() {
    cin >> t >> k;
    init();
    n = (int)t.size();
    t = " " + t;
    for (int i = 1; i <= k; i++) {
        cin >> s[i];
        len[i] = (int)s[i].size();
    }
    f[0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= k; j++) {
            if (check(i, j) == 0) continue;
            for (int l = i - len[j]; l < i; l++)
                if (f[i] > f[l] + 1) {
                    f[i] = f[l] + 1;
                    pre[i] = l;
                    a[i] = {j, i - len[j] + 1};
                }
        }
    if (f[n] == INF) cout << "-1" << endl;
    else {
        cout << f[n] << endl;
        for (int i = n; i; i = pre[i]) cout << a[i].first << " " << a[i].second << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) solve();
}

E

注意到如果 $x\equiv 0 \pmod 5$ ，则在经历一次操作后 $x$ 的末位会变为 $0$ ，此后不会再增长。所以若 $a$ 中有 $5$ 的倍数，则在把他们都变为 $10$ 的倍数之后必须要求其全都相等。

根据上面的性质特判掉含 $5$ 的倍数的情况，考虑 $x$ 的末位。

• 若其为奇数，则进行一次操作后变为偶数，且此后的所有操作不会影响其奇偶，可以当成偶数处理。

• 若其为偶数，考虑 $2\rightarrow 4\rightarrow 8\rightarrow 6\rightarrow 2$ 的变换过程，容易发现这是一个循环，且以 $+20$ 为一个循环节。

所以只需要把所有数操作至末位相同 ，要求其模 $20$ 余数全部相等即可。

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

int T, n, cnt, mx, mn, a[N];

int main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        cnt = 0, mx = -2e9, mn = 2e9;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            if (a[i] % 5 == 0) cnt++;
        }
        if (cnt && cnt != n) {
            cout << "NO" << endl;
            continue;
        }
        for (int i = 1; i <= n; i++) {
            while (a[i] % 10 != 2 && a[i] % 10) a[i] += a[i] % 10;
            if (cnt == 0) a[i] %= 20;
            mx = max(mx, a[i]);
            mn = min(mn, a[i]);
        }
        if (mx == mn) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

F

待补。

G

待补。